#leetcode题目92：反转链表II
#难度：中等
from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        if not data:
            return None
        
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        
        # 逐个为 data 内的数据创建结点,建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None:
            return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next
        print()  # 换行

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        def rev(head):
            pre, cur = None, head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
            return pre
        m = n = ListNode(0)
        n.next = head
        for _ in range(left-1):
            n = n.next
        l = n
        mid = n.next
        for _ in range(right-left+1):
            n = n.next
        r = n.next
        n.next = None
        l.next = rev(mid)
        mid.next = r
        return m.next


#测试数据
data = [1,2,3,4,5]
left = 2
right = 4
#预期输出：[1,4,3,2,5]
head = LinkList().initList(data)
solution = Solution()
LinkList().printlist(solution.reverseBetween(head,left,right))


